#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import division

# import psyco
# psyco.full()

class Solver(object):
    """Magic square solver.
   
    size : int
        Size of a row/column of the square.
    magic_sum : int
        The sum of each row, column and diagonal in a valid magic square.
    numbers : int
        Number of cells in the square.
    used : [bool]
        Keeps track of (un)used numbers in the square.
    sums : [([int], bool)]
        Contains tupels for every index of the solution.
       
        The tupels contain a list with a sum for row, column, or &#9472;where
        applicable&#9472; diagonal this index belongs to and a boolean that tells
        wether this is the index of the last cell in that row, column, or
        diagonal.
       
        The list with a single integer value is there to simulate a pointer
        to an int like in C.
    solution : [int]
        The (partial) solution as flat list.
    """
    def __init__(self, size):
        """Creates a magic square solver for given `size`."""
        self.size = size
        self.magic_sum = (size**3 + size) // 2
        self.numbers = size**2
        self.used = [False] * (self.numbers + 1)
        self.sums = [[] for dummy in xrange(self.numbers)]
        self.solution = [0] * self.numbers
       